Reorder List || Partition List

发表于

Reorder List

Question

Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,

Given {1,2,3,4}, reorder it to {1,4,2,3}.

Analysis

  • 将一个链表以中点分为两段 l1,l2，并将 l2 reverse
  • 遍历两个链表，将第二半链表中的点依次插入第一个链表中
  • 注意在遍历插入节点之前先将第一半链表最后节点置空null

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){     // Find the mid-point
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode reverseHead=slow.next;
        slow.next=null;
        reverseHead=reverse(reverseHead);
        ListNode cur=head;
        while(reverseHead!=null){
            ListNode next=cur.next;
            ListNode rnext=reverseHead.next;
            cur.next=reverseHead;
            reverseHead.next=next;
            reverseHead=rnext;
            cur=next;
        }
    }
    
    private ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode prev=new ListNode(0);
        ListNode cur=head;
        prev.next=head;
        while(cur!=null&&cur.next!=null){
            ListNode tmp=cur.next;
            cur.next=tmp.next;
            tmp.next=prev.next;
            prev.next=tmp;
        }
        return prev.next;
    }
}

Partition List

Question

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

Analysis

两个链表分别代表依次插入符合条件的节点，最后连接在一起，注意将结果链表尾节点置空。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
       ListNode s=new ListNode(0),b=new ListNode(0);
       ListNode scur=s,bcur=b;
       while(head!=null){
           if(head.val>=x){
               bcur.next=head;
               bcur=bcur.next;
           }else{
               scur.next=head;
               scur=scur.next;
           }
           head=head.next;
       }
       bcur.next=null;
       scur.next=b.next;
       return s.next;
    }
}